package com.example;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @Author loubobooo
 * @Description #199. 二叉树的右视图
 * @Date 2022/2/24
 */
public class BinaryTreeRightSideView {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    private List<Integer> list = new ArrayList<>();
    /**
     * 方法描述:给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
     * 我们按照 「根结点 -> 右子树 -> 左子树」 的顺序访问， 就可以保证每层都是最先访问最右边的节点的。
     * @param: [root]
     * @return: java.util.List<java.lang.Integer>
     * @author: loubobooo
     * @date: 2022/2/24
     */
    public List<Integer> rightSideView(TreeNode root) {
        dfs(root, 0);
        return list;
    }

    private void dfs(TreeNode node, int depth){
        if(node == null){
            return;
        }
        // 如果当前节点所在深度还没有出现在res里，说明在该深度下当前节点是第一个被访问的节点，因此将当前节点加入res中。
        // 也就是拿最右边元素->深度=size大小
        if (depth == list.size()) {
            list.add(node.val);
        }
        // 先访问 当前节点，再递归地访问 右子树 和 左子树。
        depth++;
        dfs(node.right, depth);
        dfs(node.left, depth);
    }

    public void inOrder(TreeNode treeNode){
        if(treeNode == null){
            return;
        }
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.add(treeNode);
        while(!stack.isEmpty()){
            TreeNode cur = stack.pop();
            list.add(cur.val);
            if(cur.right != null){
                stack.push(cur.right);
            }
            if(cur.left != null){
                stack.push(cur.left);
            }
        }
    }


}
